package com.leetcode.algorithm.y22.m07.w3;

/**
 * 713. 乘积小于 K 的子数组
 * 
 * https://leetcode.cn/problems/subarray-product-less-than-k/
 * 
 * @author jie.deng
 *
 */
class Question0713Solution01 {

	public int numSubarrayProductLessThanK(int[] nums, int k) {
		int cnt = 0;
		int len = nums.length;
		int left = 0;
		int right = 0;
		int mul = 1;
		while (right < len) {
			// mul是以right-1结尾的乘积小于 K 的子数组的最大乘积
			// 尝试加入right
			mul = mul * nums[right];

			// 如果乘积不小于K，则尝试从左边减少元素
			while (mul >= k && left <= right) {
				mul /= nums[left];
				left++;
			}
			// (right - left + 1) 表示以right结尾的乘积小于 K 的子数组的个数(子数组分别是[right],[right-1,right],[left,...,right-1,right])
			cnt += (right - left + 1);

			right++;
		}
		return cnt;
	}

}